package com.wpp.data_structure.skiplist;

import com.wpp.data_structure.SkipNode;

import java.util.Random;

/**
 * @author wpp25
 * @date 2021/6/12 12:59
 * @description：
 *
 *  时间复杂度 O(log(n))
 */
public class MySkipList implements SkipList{

    private int HEAD_VALUE = -1;

    // 头结点
    private SkipNode head;

    private int length;

    /**
     * 缓存 级数
     */
    private int level;

    public MySkipList() {
        head = new SkipNode(HEAD_VALUE,null,null);
        this.level = 0;
        this.length = 0;
    }

    @Override
    public boolean search(int target) {
        SkipNode preNode = get(target, head);
        return preNode != null;
    }



    @Override
    public void add(int num) {
         SkipNode currentNode = head;
        // 用于 记录 查找位置时 每次 节点下移的当前节点
        SkipNode[] arr = new SkipNode[level + 1];
        int count = -1;
         // 遍历
         while (currentNode != null) {
             // 遍历 当前level 如果 当前节点的右节点的值 小于目标值  则 当前节点右移
             while (currentNode.right != null && currentNode.right.element  < num) {
                 currentNode = currentNode .right;
             }
             count++;
             arr[count] = currentNode;
             currentNode = currentNode.down;
         }
         // 在指定位置 插入节点
        SkipNode pre = arr[count];
        SkipNode targetPosition = new SkipNode(num, pre.right, null);
        pre.right = targetPosition;
        length++;

        addIndexByCoinFlip(targetPosition,arr,count - 1);
    }

    /**
     * 根据硬币翻转决定是否 添加索引
     * @param targetPosition 新增值的目标位置
     * @param arr 记录 每次 下移前 节点的索引节点容器
     * @param count 从容器的count位置 处 创建该level 索引
     */
    private void addIndexByCoinFlip(SkipNode targetPosition, SkipNode[] arr, int count) {
        SkipNode downIndex = targetPosition;
        Random random = new Random();
        int i = random.nextInt(2); // 0 或 1

        //  包括level 内 添加索引
        while (i == 1 && level < (length >> 6)) {
            if (count >= 0) {
                SkipNode pre = arr[count];
                count--;
                SkipNode addIndexNode = new SkipNode(targetPosition.element, pre.right, downIndex);
                pre.right = addIndexNode;
                downIndex = addIndexNode;

                i = random.nextInt(2);
            } else {
                // level 外 添加索引
                SkipNode addIndexNode = new SkipNode(targetPosition.element, null, downIndex);
                head = new SkipNode(HEAD_VALUE, addIndexNode, head);
                level++;
            }
        }
    }


    // 需要优化 level - 1 的情况 fixme
    @Override
    public boolean erase(int num) {
        SkipNode preNode = get(num, head);
        boolean exist = false;
        while (preNode != null) {
            exist = true;
            SkipNode needDel = preNode.right;
            preNode.right = needDel.right;
            needDel.right = null; // help gc

            preNode = get(num,preNode.down);
        }

        if (exist) {
            length--;
        }
        return exist;
    }

    @Override
    public String print() {
        StringBuilder sb = new StringBuilder("head ->");
        SkipNode current = head;
        for (int i = 0; i < level; i++) {
            while (current.right != null) {
                sb.append(current.right.element).append(" -> ");
                current = current.right;
            }
        }



        return null;
    }

    // 从from 节点开始 遍历 当前level 是否存在 target
    private SkipNode get(int target,SkipNode from) {
        SkipNode currentNode = from;
        while (currentNode != null) {
            // 当前level 依次向右循环  若 当前节点的右节点比目标值小 当前节点右移
            while (currentNode.right != null && currentNode.right.element < target) {
                currentNode = currentNode.right;
            }
            // 判断 循环到的当前节点的右节点是否是目标值  若是 则直接返回 true  不是 则 继续循环查找
            if (currentNode.right != null && currentNode.right.element == target) {
                return currentNode;
            }
            // 当前level没有找到 往下个level 查找
            currentNode = currentNode.down;

        }
        return null;
    }



}
